package demo2;

class Solution {
    public int numIslands(char[][] grid) {
       int m = grid.length;
       int n = grid[0].length;
       int cnt = 0;
       int[][] mark = new int[grid.length][grid[0].length];
       for(int i =0;i<m;++i){
           for(int j =0;j<n;++j){
               if(grid[i][j]=='1'&&mark[i][j]==0){
                  dfs(grid,i,j,mark);
                  cnt++;
               }
           }
       }
       return cnt;
    }

    public void dfs(char[][] grid,int i,int j,int[][] mark){
        
        mark[i][j] = 1;

        int[] dx = {-1,1,0,0};
        int[] dy = {0,0,-1,1};

        for(int index = 0;index<4;++index){
            int next_i = dx[index] + i;
            int next_j = dy[index] + j;
            if(next_i<0||next_i>=grid.length||
              next_j<0||next_j>=grid[0].length){
               continue;
            }
            if((grid[next_i][next_j]=='1')&& (mark[next_i][next_j]==0)){
                dfs(grid,next_i,next_j,mark);
            }
        }
    }

    public static void main(String[] args) {
        char[][] grid = {{'1','1','0','0','0'},{'1','1','0','0','0'},
                {'0','0','1','0','0'},{'0','0','0','1','1'}};
        Solution solution = new Solution();
        solution.numIslands(grid);
    }

}